package leetcode.top100;

/**
 * 最长回文子串:使用Manacher算法
 * {@link Code05_LongestPalindrome2}
 * @date 2020/3/23 17:17
 */
public class Code647_回文子串个数2 {

    public static void main(String[] args) {
        System.out.println(countSubstrings("aaa"));
    }
    public static int countSubstrings(String s) {
        if (s == null || s.length() == 0) return 0;
        s = getModify(s);
        int rightR = 0;
        int rightCenter = 0;
        int max = 0;
        int maxCenter = 0;
        int[] pCenter = new int[s.length()];
        for (int i = 0; i < s.length(); i++) {
            if(i <= rightR) {
                //情况2的case1，case2，和case3部分
                pCenter[i] = Math.min(pCenter[2 * rightCenter - i],rightR - i +1);
            }else {
                pCenter[i] = 1;
            }
            //判断是否能扩。
            while (i-pCenter[i] >= 0 && i + pCenter[i] < s.length()){
                //情况2的case1和case2必定不会进入
                if(s.charAt(i-pCenter[i]) == s.charAt(i+pCenter[i])){
                    pCenter[i]++;
                }else {
                    break;
                }
            }
            //更新半径
            if(i + pCenter[i] - 1 > rightR){
                rightR = i + pCenter[i] - 1;
                rightCenter = i;
            }
            //最大值
            if(pCenter[i] > max){
                max = pCenter[i];
                maxCenter = i;
            }

        }
        int res = 0;
        //计算每个位置的实际回文串个数
        //如果以字符为中心  #3#2#1#2#3#  p=6,实际上是3
        //如果以#为中心  #3#2#1#1#2#3#  p=7,实际上是3 所以最后是 p/2
        for (int num : pCenter) {
            res += num/2;
        }
        return res;

    }
    private static String getModify(String s) {
        StringBuffer sb = new StringBuffer("#");
        for (int i = 0; i < s.length(); i++) {
            sb.append(s.charAt(i)).append("#");
        }
        return sb.toString();
    }




}
